package com.elloe.数组.二分查找;

import org.junit.jupiter.api.Test;

/**
 * @author ElloeStudy(Sifa Zhang)
 * @create 2022-01-02 10:15
 * To: 真常应物，真常得性，常清常静，常清静矣
 */
public class binarySearch {
    // 数组基础
    @Test
    public void test1() {
        // 数组下标都是从0开始的。
        // 数组内存空间的地址是连续的
        // 数组的元素是不能删的，只能覆盖(在删除或者添加元素的时候，就需要移动其他后面的元素)
        // 数组的元素不能删除，只能覆盖

        // Java是没有指针的，不对程序员暴露其地址，寻址操作完全交给虚拟机
        // [I@6b09bb57   这里的地址不是真正的地址，是经过处理的地址
        int[][] arr = {{1, 2, 3}, {3, 4, 5}, {6, 7, 8}, {9, 9, 9}};
        System.out.println(arr[0]);
        System.out.println(arr[1]);
        System.out.println(arr[2]);
    }

    // 704 二分查找
    // 二分查找（左闭右开）
    // 数组为有序数组(线性表)，数组里面没有重复的元素
    // 处理问题的边界
    @Test
    public void test2() {
        int[] nums = {1, 2, 3, 4, 7, 9, 10};
        int target = 9;
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);  // 类似于 (left+right)/2
            if (nums[mid] == target) {
                // 只有当 nums[mid] == target 时，退出循环
                System.out.println(mid);
                return ;
            }
            else if (nums[mid]<target){
                left = mid + 1;  // 假如中间数小于目标值，则说明在右边区间
            }
            else if (nums[mid]>target){
                right = mid ;  // 假如中间数大于目标值，则说明在左边区间
            }
        }
        System.out.println(-1);
        // 在while循环里面1没有找到target，则输出-1，代表没有找到
        return ;
    }

    @Test
    public void test3(){
        int x = 6;
        int min = 0 , max = x;
        while(min<max){
            int mid = min + ((max-min)>>1);
            if(mid*mid > x){
                max = mid;
            }else if(mid*mid < x){
                min = min+1;
            }
            else if(mid*mid == x){
                System.out.println(mid);
                return ;
            }
        }
        System.out.println(min-1);
        return ;
    }

}
